#include "config.h"

#include <clx/libECM.h>
#include <clx/ecm_list.h>

#include "blockcache.h"

#undef PARANOIA

static LIST_HEAD(free_list);
static LIST_HEAD(intervals);

static ecm_hashtable_t	hash_session;

/* For simplicity, do not care performance */

struct _session;

typedef struct {
	ecm_uint32	size;
	ecm_uint32	bid_head;
	ecm_uint32	bid_tail;
	struct _session	*follower;
	struct _session	*precedent;
	struct list_head	cblks;
	/* for sorting */
	struct list_head	list;
	struct list_head	list_media;
} interval_t;

typedef struct {
	ecm_uint32	mid;
	ecm_uint32	bid_max;
	struct list_head	intervals;
} media_t;

typedef struct {
	bcache_t	*bcache;
	struct list_head	list;
} cblk_t;

typedef struct _session {
	ecm_uint32	sid;
	ecm_uint32	bid;
	interval_t	*preceding;
	interval_t	*following;
	media_t		*media;
} session_t;

static ecm_ptrs_t	*ptrs_media;

#ifdef PARANOIA

static void
check_interval_sanity(interval_t *interval)
{
	session_t	*follower, *precedent;

	follower = interval->follower;
	precedent = interval->precedent;

	if (follower != NULL) {
		ECMASSERT(follower->following == interval);
		ECMASSERT(interval->bid_head == follower->bid);
	}

	if (precedent != NULL) {
		ECMASSERT(precedent->preceding == interval);
		ECMASSERT(interval->bid_tail == precedent->bid);
	}

	if (follower != NULL && precedent != NULL)
		ECMASSERT(follower->bid <= precedent->bid);
}

static void
check_all_interval_sanity(void)
{
	interval_t	*interval;
	struct list_head	*lp;

	list_for_each (lp, &intervals) {
		interval = list_entry(lp, interval_t, list);
		check_interval_sanity(interval);
	}
}

#define CHECK_ALL_INTERVAL_SANITY()	check_all_interval_sanity()

#else

#define CHECK_ALL_INTERVAL_SANITY(cset)	do {} while (0)

#endif

static void
collect_cache(interval_t *interval)
{
	///TODO
}

/**
 * sort interval again
 */
static void
sort_interval(interval_t *interval, ECMBOOL forward)
{
	struct list_head	*lp, *first;
	ecm_uint32	size;
	interval_t	*intv_list;

	ECMASSERT(!list_empty(&interval->list));

	first = (forward) ? interval->list.next : interval->list.prev;
	list_del(&interval->list);

	size = interval->size;

	if (forward) {
		for (lp = first; lp != &intervals; lp = lp->next) {
			intv_list = list_entry(lp, interval_t, list);
			if (size > intv_list->size) {
				list_add_tail(&interval->list, &intv_list->list);
				return;
			}
		}
		list_add_tail(&interval->list, &intervals);
	}
	else {
		for (lp = first; lp != &intervals; lp = lp->prev) {
			intv_list = list_entry(lp, interval_t, list);
			if (size < intv_list->size) {
				list_add(&interval->list, &intv_list->list);
				return;
			}
		}
		list_add(&interval->list, &intervals);
	}
}

static interval_t *
create_interval(session_t *precedent, session_t *follower, ecm_uint32 bid_head, ecm_uint32 bid_tail)
{
	interval_t	*interval;

	ECMASSERT(precedent == NULL || follower == NULL || precedent->bid >= follower->bid);

	interval = (interval_t *)ecm_malloc(sizeof(interval_t));
	ECMASSERT(interval != NULL);

	interval->size = bid_tail - bid_head;
	interval->bid_head = bid_head;
	interval->bid_tail = bid_tail;
	interval->follower = follower;
	interval->precedent = precedent;

	if (follower != NULL)
		follower->following = interval;
	if (precedent != NULL)
		precedent->preceding = interval;

	INIT_LIST_HEAD(&interval->cblks);
	INIT_LIST_HEAD(&interval->list);
	INIT_LIST_HEAD(&interval->list_media);

	return interval;
}

static void
free_interval(interval_t *interval)
{
	list_del(&interval->list);
	list_del(&interval->list_media);
	ecm_free(interval);
}

static void
build_head_interval(session_t *precedent, interval_t *following)
{
	interval_t	*interval;
	media_t	*media = precedent->media;

	ECMASSERT(precedent != NULL);
	ECMASSERT(precedent->preceding == NULL);

	interval = create_interval(precedent, NULL, 1, precedent->bid);

	list_add(&interval->list, &intervals);
	sort_interval(interval, ECM_TRUE);

	ECMASSERT(list_entry(media->intervals.next, interval_t, list_media) == following);
	ECMASSERT(list_empty(&media->intervals) || interval->bid_tail <= following->bid_head);

	list_add(&interval->list_media, &media->intervals);

	ECMASSERT(following->follower == NULL);
	following->follower = precedent;
	precedent->following = following;

	collect_cache(interval);
}

static void
build_tail_interval(session_t *follower, interval_t *preceding)
{
	interval_t	*interval;
	media_t	*media = follower->media;

	ECMASSERT(follower != NULL);
	ECMASSERT(follower->following == NULL);

	interval = create_interval(NULL, follower, follower->bid, media->bid_max);

	list_add(&interval->list, &intervals);
	sort_interval(interval, ECM_TRUE);

	ECMASSERT(list_entry(media->intervals.prev, interval_t, list_media) == preceding);
	ECMASSERT(list_empty(&media->intervals) || interval->bid_head >= preceding->bid_tail);

	list_add_tail(&interval->list_media, &media->intervals);

	ECMASSERT(preceding->precedent == NULL);
	preceding->precedent = follower;
	follower->preceding = preceding;

	collect_cache(interval);
}

static void
build_initial_intervals(session_t *session)
{
	interval_t	*preceding, *following;
	media_t	*media = session->media;

	ECMASSERT(session->preceding == NULL && session->following == NULL);

	preceding = create_interval(session, NULL, 1, session->bid);
	following = create_interval(NULL, session, session->bid, media->bid_max);

	list_add(&preceding->list, &intervals);
	list_add(&following->list, &intervals);
	sort_interval(following, ECM_TRUE);

	list_add(&following->list_media, &media->intervals);
	list_add(&preceding->list_media, &media->intervals);

	collect_cache(preceding);
	collect_cache(following);
}

static void
build_self_interval(session_t *session, session_t *follower, session_t *precedent)
{
	interval_t	*interval;

	if (follower != NULL) {
		interval_t	*preceding = follower->preceding;

		ECMASSERT(preceding != NULL);

		interval = create_interval(follower, session, session->bid, follower->bid);

		preceding->precedent = session;
		session->preceding = preceding;
		follower->preceding = interval;

		list_add_tail(&interval->list_media, &follower->following->list_media);
	}
	else {
		interval_t	*following = precedent->following;

		ECMASSERT(following != NULL);

		interval = create_interval(session, precedent, precedent->bid, session->bid);

		following->follower = session;
		session->following = following;
		precedent->following = interval;

		list_add(&interval->list_media, &precedent->preceding->list_media);
	}

	list_add(&interval->list, &intervals);
	sort_interval(interval, ECM_TRUE);

	collect_cache(interval);
}

/**
 * @brief get cache blocks from splitted interval
 */
static void
split_cblks(interval_t *interval, session_t *session)
{
	ecm_uint32	bid = session->bid;
	cblk_t	*cblk;
	struct list_head	*pcblks;
	struct list_head	*lp, *next;
	interval_t	*preceding = session->preceding;

	pcblks = &preceding->cblks;
	list_for_each_n (lp, &interval->cblks, next) {
		cblk = list_entry(lp, cblk_t, list);

		if (bid < cblk->bcache->bid)
			return;

		list_del(&cblk->list);
		list_add_tail(&cblk->list, pcblks);
	}
}

static void
split_interval(interval_t *interval, session_t *session)
{
	session_t	*follower, *precedent;
	interval_t	*interval_new;
	ecm_uint32	bid_head;

	follower = interval->follower;
	precedent = interval->precedent;

	bid_head = follower ? follower->bid: 1;
	interval_new = create_interval(session, follower, bid_head, session->bid);

	interval->follower = session;
	session->following = interval;

	sort_interval(interval, ECM_TRUE);

	list_add(&interval_new->list, &intervals);
	sort_interval(interval_new, ECM_TRUE);

	list_add_tail(&interval_new->list_media, &interval->list_media);
	split_cblks(interval, session);
}

/**
 * @brief find the nearst interval
 *
 * Find the earliest interval if bid is less than or equal to the follower of all intervals.
 * Or find the lastest interval if bid is greater than or equal to the precedent.
 *
 * TOOD: Currently support forward search only.
 */
static interval_t *
find_interval(ecm_uint32 mid, ecm_uint32 bid, interval_t **phead, interval_t **ptail, interval_t *hint)
{
	media_t	*media;
	interval_t	*interval;
	struct list_head	*lp;

	ECMASSERT(bid > 0);

	media = ecm_ptrs_get(ptrs_media, mid);
	ECMASSERT(media != NULL);

	if (hint == NULL) {
		lp = media->intervals.next;
		interval = list_entry(lp, interval_t, list_media);
		if (bid < interval->bid_head) {
			*phead = interval;
			return NULL;
		}
	}
	else {
		ECMASSERT(bid <= hint->bid_tail);
		lp = &hint->list_media;
	}

	for (; lp != &media->intervals; lp = lp->next) {
		interval = list_entry(lp, interval_t, list_media);

		ECMASSERT(interval->bid_head <= interval->bid_tail);

		if (bid == interval->bid_head || bid < interval->bid_tail)
			return interval;
	}

	if (interval->bid_tail == bid)
		return interval;

	*phead = NULL;
	*ptail = interval;
	return NULL;
}

/**
 * @brief Insert newly or cut-out session to form a interval.
 */
static void
putdown_session(session_t *session, interval_t *hint)
{
	media_t		*media = session->media;
	interval_t	*interval, *interval_head, *interval_tail;

	if (list_empty(&media->intervals)) {
		/* media has no interval */
		build_initial_intervals(session);
		return;
	}

	interval = find_interval(media->mid, session->bid, &interval_head, &interval_tail, hint);
	if (interval == NULL) {
		if (interval_head)
			build_head_interval(session, interval_head);
		else
			build_tail_interval(session, interval_tail);
		return;
	}

	if (session->bid == interval->bid_head) {
		session_t	*follower = interval->follower;

		ECMASSERT(follower == NULL || follower->bid == session->bid);
		if (follower == NULL)
			build_head_interval(session, interval);
		else
			build_self_interval(session, follower, NULL);
	}
	else if (session->bid == interval->bid_tail) {
		session_t	*precedent = interval->precedent;

		ECMASSERT(precedent == NULL || precedent->bid == interval->bid_tail);
		if (precedent == NULL)
			build_tail_interval(session, interval);
		else
			build_self_interval(session, NULL, precedent);
	}
	else {
		split_interval(interval, session);
	}

	ECMASSERT(session->following != NULL && session->preceding != NULL);
}

static session_t *
create_session(ecm_uint32 sid, ecm_uint32 mid, ecm_uint32 bid)
{
	session_t	*session;

	session = (session_t *)ecm_malloc(sizeof(session_t));
	session->sid = sid;
	session->bid = bid;
	session->preceding = NULL;
	session->following = NULL;
	session->media = (media_t *)ecm_ptrs_get(ptrs_media, mid);
	ECMASSERT(session->media != NULL);

	ecm_hashtable_insert(hash_session, session, sizeof(sid), &sid);

	return session;
}

static void
free_session(session_t *session)
{
	ecm_hashtable_remove(hash_session, sizeof(ecm_uint32), &session->sid);
	ecm_free(session);
}

/**
 * @brief cut out session. It may cause intervals to be merged or deleted.
 */
static void
cut_session(session_t *session)
{
	interval_t	*preceding, *following;
	session_t	*precedent = NULL;

	preceding = session->preceding;
	following = session->following;

	ECMASSERT(preceding != NULL && following != NULL);

	precedent = following->precedent;
	preceding->precedent = precedent;
	preceding->bid_tail = following->bid_tail;

	if (precedent != NULL)
		precedent->preceding = preceding;
	preceding->size += following->size;

	/* merge cblks */
	list_splice(&following->cblks, preceding->cblks.prev);

	free_interval(following);

	sort_interval(preceding, ECM_FALSE);

	session->preceding = NULL;
	session->following = NULL;
}

static session_t *
get_session(ecm_uint32 sid, ecm_uint32 mid, ecm_uint32 bid)
{
	session_t	*session;

	session = (session_t *)ecm_hashtable_get(hash_session, sizeof(sid), &sid);
	if (session == NULL) {
		session = create_session(sid, mid, bid);
		putdown_session(session, NULL);
	}
	else {
		if (bid != session->bid + 1) {
			cut_session(session);
			session->bid = bid;
			putdown_session(session, NULL);
		}
		else
			session->bid = bid;
	}

	return session;
}

static void
insert_cblk(interval_t *interval, cblk_t *cblk)
{
	struct list_head	*lp;
	cblk_t	*cblk_list;

	ECMASSERT(list_empty(&cblk->list));

	for (lp = interval->cblks.prev; lp != &interval->cblks; lp = lp->prev) {
		cblk_list = list_entry(lp, cblk_t, list);

		ECMASSERT(cblk_list->bcache->mid == cblk->bcache->mid);
		ECMASSERT(cblk_list->bcache->bid != cblk->bcache->bid);

		if (cblk->bcache->bid > cblk_list->bcache->bid) {
			list_add(&cblk->list, &cblk_list->list);
			return;
		}
	}
	list_add(&cblk->list, &interval->cblks);
}

static const char *
vic_init(ecm_uint32 cache_blksize, ecm_uint32 n_caches)
{
	ptrs_media = ecm_ptrs_new(16);

	hash_session = ecm_hashtable_create(32);

	return "VIC";
}

static void
vic_create(bcache_t *bcache)
{
	cblk_t	*cblk;

	cblk = (cblk_t *)ecm_malloc(sizeof(cblk_t));
	bcache->priv = cblk;
	cblk->bcache = bcache;
	list_add(&cblk->list, &free_list);
}

static void
vic_hit(bcache_t *bcache)
{
	cblk_t	*cblk = (cblk_t *)bcache->priv;

	list_del_init(&cblk->list);
}

static bcache_t *
vic_replace(ecm_uint32 mid, ecm_uint32 bid)
{
	cblk_t	*cblk;

	if (!list_empty(&free_list))
		cblk = list_entry(free_list.next, cblk_t, list);
	else {
		interval_t	*interval;
		struct list_head	*lp;

		list_for_each (lp, &intervals) {
			interval = list_entry(lp, interval_t, list);
			if (!list_empty(&interval->cblks)) {
				cblk = list_entry(interval->cblks.prev, cblk_t, list);
				goto out;
			}
		}
		return NULL;
	}
out:
	list_del_init(&cblk->list);
	return cblk->bcache;
}

static void
vic_put(ecm_uint32 sid, bcache_t *bcache)
{
	session_t	*session;
	cblk_t	*cblk = (cblk_t *)bcache->priv;
	interval_t	*preceding;

	session = (session_t *)ecm_hashtable_get(hash_session, sizeof(sid), &sid);
	ECMASSERT(session != NULL);

	preceding = session->preceding;
	if (preceding == NULL) {
		build_head_interval(session, NULL);
		preceding = session->preceding;
	}

	insert_cblk(preceding, cblk);
}

static void
vic_access(ecm_uint32 sid, ecm_uint32 mid, ecm_uint32 bid)
{
	session_t	*session;
	interval_t	*preceding, *following;
	ecm_uint32	old_size, new_size;

	session = get_session(sid, mid, bid);
	ECMASSERT(session != NULL);

	preceding = session->preceding;
	following = session->following;
	ECMASSERT(preceding != NULL && following != NULL);

	/* check if a follower has preceded its precedent */
	if (session->bid > following->bid_tail) {
		cut_session(session);
		putdown_session(session, following);
		return;
	}

	ECMASSERT(preceding->precedent == session);
	ECMASSERT(session->bid >= preceding->bid_head);

	old_size = preceding->size;
	new_size = bid - preceding->bid_head;

	if (old_size != new_size) {
		preceding->size = new_size;
		sort_interval(preceding, old_size > new_size);
	}
	preceding->bid_tail = bid;

	ECMASSERT(following->follower == session);
	ECMASSERT(session->bid <= following->bid_tail);

	old_size = following->size;
	new_size = following->bid_tail - bid;

	if (old_size != new_size) {
		following->size = new_size;
		sort_interval(following, old_size > new_size);
	}
	following->bid_head = bid;

	ECMASSERT(preceding->follower == NULL || preceding->follower->bid == preceding->bid_head);
	ECMASSERT(following->precedent == NULL || following->precedent->bid == following->bid_tail);

	CHECK_ALL_INTERVAL_SANITY();
}

static void
vic_leave(ecm_uint32 sid)
{
	session_t	*session;

	session = (session_t *)ecm_hashtable_get(hash_session, sizeof(sid), &sid);
	ECMASSERT(session != NULL);

	cut_session(session);
	free_session(session);
}

static void
vic_add_media(ecm_uint32 bid_max)
{
	media_t		*media;

	media = (media_t *)ecm_malloc(sizeof(media_t));
	media->mid = ptrs_media->count + 1;
	media->bid_max = bid_max;
	INIT_LIST_HEAD(&media->intervals);
	ecm_ptrs_add(ptrs_media, media);
}

static void
vic_fini(void)
{
}

blockcache_op_t	bcache_op = {
	vic_init,
	NULL,
	NULL,
	vic_add_media,

	vic_create,
	vic_hit,
	vic_replace,
	vic_put,

	vic_access,
	vic_leave,
	vic_fini
};
